| Content On This Page | ||
|---|---|---|
| Empty Relation and Universal Relation | Identity Relation | Reflexive Relation |
| Symmetric Relation | Transitive Relation | Equivalence Relation and Equivalence Classes |
Types of Relations
Empty Relation and Universal Relation
When considering relations on a single set $A$ (i.e., subsets of $A \times A$), there are two extreme cases based on how many ordered pairs from $A \times A$ are included in the relation. These are the empty relation and the universal relation.
1. Empty Relation (Void Relation)
A relation $R$ on a set $A$ is called the empty relation if it contains no ordered pairs from $A \times A$. This means that no element of set $A$ is related to any element of set $A$ under this relation.
Definition:
The empty relation $R$ on set $A$ is defined as the empty set itself, considered as a subset of $A \times A$.
$R = \emptyset$, where $\emptyset \subseteq A \times A$
The condition that defines an empty relation is one that is never satisfied by any pair of elements from the set $A$.
Example 1. Let $A = \{1, 2, 3, 4, 5\}$. Define a relation $R$ on $A$ by $R = \{(a, b) \mid a, b \in A \text{ and } a - b = 6\}$. Is R the empty relation?
Answer:
Given: $A = \{1, 2, 3, 4, 5\}$. Relation $R = \{(a, b) \mid a, b \in A, a - b = 6\}$.
To Determine: Is R the empty relation?
Solution:
For R to be non-empty, there must exist at least one ordered pair $(a, b)$ such that $a \in A$, $b \in A$, and $a - b = 6$.
Let's consider the possible differences between elements $a$ and $b$ from set $A$. The largest possible value for $a$ is 5, and the smallest possible value for $b$ is 1. The maximum difference $a - b$ would be $5 - 1 = 4$.
The smallest possible value for $a$ is 1, and the largest possible value for $b$ is 5. The minimum difference $a - b$ would be $1 - 5 = -4$.
So, for any $a, b \in A$, the difference $a - b$ will be in the range $[-4, 4]$.
Since $6$ is outside this range, the condition $a - b = 6$ cannot be satisfied by any pair $(a, b)$ where $a, b \in A$.
Therefore, the set of ordered pairs $R$ satisfying the condition is empty.
$R = \emptyset$
Thus, R is the empty relation on set A.
2. Universal Relation
A relation $R$ on a set $A$ is called the universal relation if it contains all possible ordered pairs from $A \times A$. This means that every element of set $A$ is related to every element of set $A$ (including itself) under this relation.
Definition:
The universal relation $R$ on set $A$ is defined as the entire Cartesian product $A \times A$.
$R = A \times A$
The condition that defines a universal relation is one that is always satisfied by any pair of elements from the set $A$.
Example 2. Let $A = \{a, b\}$. Define a relation $R$ on $A$ by $R = \{(x, y) \mid x, y \in A \text{ and } x \text{ and } y \text{ are either equal or not equal}\}$. Is R the universal relation?
Answer:
Given: $A = \{a, b\}$. Relation $R = \{(x, y) \mid x, y \in A \text{ and } x \text{ and } y \text{ are either equal or not equal}\}$.
To Determine: Is R the universal relation?
Solution:
The Cartesian product $A \times A$ is the set of all possible ordered pairs of elements from A:
$A \times A = \{(a, a), (a, b), (b, a), (b, b)\}$
The relation $R$ includes all pairs $(x, y)$ where $x \in A$, $y \in A$, and the condition "$x$ and $y$ are either equal or not equal" is true.
Let's check this condition for every pair in $A \times A$:
- For $(a, a)$: $a$ and $a$ are equal. The condition "equal or not equal" is true. So, $(a, a) \in R$.
- For $(a, b)$: $a$ and $b$ are not equal (assuming $a \neq b$). The condition "equal or not equal" is true. So, $(a, b) \in R$.
- For $(b, a)$: $b$ and $a$ are not equal. The condition "equal or not equal" is true. So, $(b, a) \in R$.
- For $(b, b)$: $b$ and $b$ are equal. The condition "equal or not equal" is true. So, $(b, b) \in R$.
Since the condition "x and y are either equal or not equal" is always true for any elements $x, y$ from $A$, the relation $R$ contains all ordered pairs from $A \times A$.
$R = A \times A$
Thus, R is the universal relation on set A.
The empty relation and the universal relation are sometimes referred to as the trivial relations on a set because their structure is entirely determined by the set itself, without any specific rule imposing further restrictions.
Identity Relation
The identity relation is a specific type of relation on a set $A$ where each element is related only to itself and to no other element.
Definition of Identity Relation
The identity relation on a non-empty set $A$, denoted by $I_A$ or $\Delta_A$, is the relation where every element of $A$ is related to itself and only to itself.
Set Form:
The identity relation $I_A$ is the set of all ordered pairs $(a, a)$ such that $a$ is an element of $A$.
$I_A = \{ (a, a) \mid a \in A \}$
In the identity relation, an element $a \in A$ is related to an element $b \in A$ if and only if $a=b$.
Example 3. Let $A = \{p, q, r\}$. Find the identity relation $I_A$ on set A.
Answer:
Given: Set $A = \{p, q, r\}$.
To Find: The identity relation $I_A$ on A.
Solution:
The identity relation $I_A$ consists of all ordered pairs $(a, a)$ where $a$ is an element of $A$.
The elements of A are $p, q, r$.
The pairs $(a, a)$ for these elements are $(p, p), (q, q), (r, r)$.
Therefore, the identity relation on A is:
$I_A = \{(p, p), (q, q), (r, r)\}$
This relation is a subset of $A \times A = \{(p, p), (p, q), (p, r), (q, p), (q, q), (q, r), (r, p), (r, q), (r, r)\}$.
For the identity relation $I_A$ on a set $A$:
- The Domain$(I_A)$ is $A$.
- The Range$(I_A)$ is $A$.
- The Codomain is $A$.
Summary for Competitive Exams
Relations on a set A ($R \subseteq A \times A$):
- Empty Relation: $R = \emptyset$. No element is related to any element.
- Universal Relation: $R = A \times A$. Every element is related to every element.
- Identity Relation ($I_A$): $R = \{ (a, a) \mid a \in A \}$. Each element is related only to itself.
- Trivial relations: Empty and Universal relations.
Reflexive Relation
A relation $R$ on a set $A$ possesses the property of reflexivity if every element in the set $A$ is related to itself under the relation $R$. This is a fundamental property of relations on a single set.
Definition of Reflexive Relation
A relation $R$ on a set $A$ is said to be reflexive if and only if for every element $a$ belonging to set $A$, the ordered pair $(a, a)$ is an element of the relation $R$.
Formal Condition:
A relation $R$ on $A$ is reflexive $\iff \forall a \in A, (a, a) \in R$
This condition must hold for *every* element in the set $A$. If there is even one element $a_0 \in A$ for which the pair $(a_0, a_0)$ is not in $R$, then the relation $R$ is not reflexive.
Another way to state the condition for reflexivity is that the identity relation $I_A$ must be a subset of $R$.
$R \text{ is reflexive } \iff I_A \subseteq R$
A reflexive relation must contain all the pairs $(a, a)$ for $a \in A$, but it can also contain other pairs $(a, b)$ where $a \neq b$.
How to Check if a Relation is Reflexive
To check if a given relation $R$ on a set $A$ is reflexive, follow these steps:
- Identify all the elements that are in the set $A$. Let these be $a_1, a_2, a_3, ...$.
- Form the set of identity pairs for A: $I_A = \{(a_1, a_1), (a_2, a_2), (a_3, a_3), ...\}$.
- Check if every pair in $I_A$ is present in the given relation $R$.
- If all pairs $(a, a)$ for every $a \in A$ are found in $R$, then $R$ is reflexive.
- If even one pair $(a_i, a_i)$ from $I_A$ is missing from $R$, then $R$ is not reflexive.
Note: The definition of reflexivity depends only on whether all $(a, a)$ pairs are present. The presence or absence of pairs $(a, b)$ where $a \neq b$ does not affect whether the relation is reflexive or not.
Example 4. Let $A = \{5, 6, 7\}$. Determine if the following relations on A are reflexive:
(i) $R_1 = \{(5, 5), (6, 6), (7, 7), (5, 6), (6, 7)\}$
(ii) $R_2 = \{(5, 5), (6, 6), (7, 6), (7, 7)\}$
(iii) $R_3 = \{(5, 5), (5, 6), (6, 5), (6, 6), (7, 7)\}$
(iv) $R_4 = \{(a, b) \in A \times A \mid a < b\}$
(v) $R_5 = \{(a, b) \in A \times A \mid a \le b\}$
(vi) $R_6 = \emptyset$ (the empty relation)
(vii) $R_7 = A \times A$ (the universal relation)
Answer:
Given: Set $A = \{5, 6, 7\}$. For a relation on A to be reflexive, it must contain the identity pairs for A, which are $I_A = \{(5, 5), (6, 6), (7, 7)\}$. We need to check if $I_A \subseteq R$ for each relation.
- (i) $R_1 = \{(5, 5), (6, 6), (7, 7), (5, 6), (6, 7)\}$
Check for required pairs: $(5, 5) \in R_1$? Yes. $(6, 6) \in R_1$? Yes. $(7, 7) \in R_1$? Yes.
Since all pairs $(a, a)$ for $a \in A$ are in $R_1$, the relation $R_1$ is reflexive.
- (ii) $R_2 = \{(5, 5), (6, 6), (7, 6), (7, 7)\}$
Check for required pairs: $(5, 5) \in R_2$? Yes. $(6, 6) \in R_2$? Yes. $(7, 7) \in R_2$? Yes.
All pairs $(a, a)$ for $a \in A$ are in $R_2$. The relation $R_2$ is reflexive.
- (iii) $R_3 = \{(5, 5), (5, 6), (6, 5), (6, 6), (7, 7)\}$
Check for required pairs: $(5, 5) \in R_3$? Yes. $(6, 6) \in R_3$? Yes. $(7, 7) \in R_3$? Yes.
All pairs $(a, a)$ for $a \in A$ are in $R_3$. The relation $R_3$ is reflexive.
- (iv) $R_4 = \{(a, b) \in A \times A \mid a < b\}$
We need to check if $(a, a) \in R_4$ for all $a \in A$. The condition for $(a, a) \in R_4$ is $a < a$.
Is $5 < 5$? No. Is $6 < 6$? No. Is $7 < 7$? No.
Since $(5, 5) \notin R_4$, the relation $R_4$ is not reflexive.
(In roster form, $R_4 = \{(5, 6), (5, 7), (6, 7)\}$).
- (v) $R_5 = \{(a, b) \in A \times A \mid a \le b\}$
We need to check if $(a, a) \in R_5$ for all $a \in A$. The condition for $(a, a) \in R_5$ is $a \le a$.
Is $5 \le 5$? Yes. So $(5, 5) \in R_5$.
Is $6 \le 6$? Yes. So $(6, 6) \in R_5$.
Is $7 \le 7$? Yes. So $(7, 7) \in R_5$.
Since $a \le a$ is true for all $a \in A$, all pairs $(a, a)$ are in $R_5$. The relation $R_5$ is reflexive.
(In roster form, $R_5 = \{(5, 5), (5, 6), (5, 7), (6, 6), (6, 7), (7, 7)\}$).
- (vi) $R_6 = \emptyset$
The empty relation contains no pairs. The required pairs for reflexivity are $(5, 5), (6, 6), (7, 7)$. None of these are in $R_6$.
The empty relation is not reflexive on a non-empty set A.
(Note: If A were the empty set, the empty relation on A would vacuously be reflexive).
- (vii) $R_7 = A \times A$
The universal relation contains all possible pairs $(a, b)$ where $a, b \in A$. This includes all pairs $(a, a)$ where $a \in A$.
Since $A \times A = \{(5, 5), (5, 6), (5, 7), (6, 5), (6, 6), (6, 7), (7, 5), (7, 6), (7, 7)\}$, all of $(5, 5), (6, 6), (7, 7)$ are present.
The universal relation is always reflexive.
Summary for Competitive Exams
Relations on a set A ($R \subseteq A \times A$):
- Empty Relation ($R=\emptyset$): No element related to any element.
- Universal Relation ($R=A \times A$): Every element related to every element.
- Identity Relation ($I_A = \{(a,a) \mid a \in A\}$): Each element related only to itself.
- Reflexive Relation: $R$ is reflexive $\iff \forall a \in A, (a, a) \in R$. Equivalently, $I_A \subseteq R$.
Checking Reflexivity: Verify that all pairs $(a,a)$ for every $a$ in the *base set* A are present in R.
- Universal Relation is always reflexive.
- Identity Relation is always reflexive.
- Empty Relation on a non-empty set is NOT reflexive.
- Relation $a < b$ on any non-empty set is NOT reflexive.
- Relation $a \le b$ on any non-empty set is reflexive.
- Relation $a=b$ on any non-empty set is reflexive (it's the identity relation).
Symmetric Relation
A relation $R$ on a set $A$ is considered symmetric if the existence of a relationship from an element $a$ to an element $b$ guarantees the existence of the same relationship from $b$ back to $a$. It implies a kind of "two-way street" for the relationship.
Definition of Symmetric Relation
A relation $R$ on a set $A$ is said to be symmetric if and only if for all elements $a$ and $b$ in set $A$, whenever the ordered pair $(a, b)$ is in the relation $R$, the ordered pair $(b, a)$ must also be in $R$.
Formal Condition:
A relation $R$ on $A$ is symmetric $\iff \forall a, b \in A, (a, b) \in R \implies (b, a) \in R$
If $(a, b) \in R$, the condition requires $(b, a)$ to be in $R$. If $(a, b) \notin R$, the condition $(a, b) \in R \implies (b, a) \in R$ is vacuously true for that pair and its reverse, so it doesn't affect symmetry.
The condition applies only to pairs that *are* in the relation R.
Important Notes:
- For pairs of the form $(a, a)$, the condition for symmetry states: if $(a, a) \in R$, then $(a, a)$ must be in $R$. This is always true. Therefore, pairs where the first and second components are the same (diagonal elements in a table representation) never violate the symmetry property. Symmetry is only about pairs $(a, b)$ where $a \neq b$.
- If a relation $R$ contains an ordered pair $(a, b)$ where $a \neq b$, but does not contain the pair $(b, a)$, then the relation is not symmetric.
- The empty relation ($\emptyset$) on any set A is symmetric because the premise $(a, b) \in \emptyset$ is always false, making the implication vacuously true for all $a, b \in A$.
- The universal relation ($A \times A$) on any set A is symmetric because if $(a, b) \in A \times A$, then $(b, a)$ is also always in $A \times A$.
- The identity relation ($I_A$) on any set A is symmetric because it only contains pairs of the form $(a, a)$. If $(a, a) \in I_A$, then its reverse $(a, a)$ is also in $I_A$.
How to Check if a Relation is Symmetric
To check if a given relation $R$ on a set $A$ is symmetric, follow these steps:
- Go through each ordered pair $(a, b)$ that is present in the relation $R$.
- If $a = b$ for a pair $(a, b) \in R$, move to the next pair. These pairs do not affect symmetry.
- If $a \neq b$ for a pair $(a, b) \in R$, check if the reversed pair $(b, a)$ is also present in $R$.
- If for every pair $(a, b) \in R$, the reversed pair $(b, a)$ is also in $R$, the relation is symmetric.
- If you find even one pair $(a, b) \in R$ (where $a \neq b$) such that $(b, a) \notin R$, stop. The relation is not symmetric.
Example 5. Let $A = \{1, 2, 3\}$. Determine if the following relations on A are symmetric:
(i) $R_1 = \{(1, 1), (1, 2), (2, 1), (3, 3)\}$
(ii) $R_2 = \{(1, 2), (2, 3), (3, 1)\}$
(iii) $R_3 = \{(1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3, 2)\}$
(iv) $R_4 = \{(a, b) \in A \times A \mid a + b = 4\}$
(v) $R_5 = \{(a, b) \in A \times A \mid a \le b\}$
Answer:
Given: Set $A = \{1, 2, 3\}$.
- (i) $R_1 = \{(1, 1), (1, 2), (2, 1), (3, 3)\}$
Check pairs where $a \neq b$:
- $(1, 2) \in R_1$. Is $(2, 1) \in R_1$? Yes.
- $(2, 1) \in R_1$. Is $(1, 2) \in R_1$? Yes.
Pairs $(1, 1)$ and $(3, 3)$ do not need checking for reverse pairs with different components. All required conditions hold.
The relation $R_1$ is symmetric.
- (ii) $R_2 = \{(1, 2), (2, 3), (3, 1)\}$
Check pairs where $a \neq b$:
- $(1, 2) \in R_2$. Is $(2, 1) \in R_2$? No.
Since we found a pair $(1, 2)$ in $R_2$ but its reverse $(2, 1)$ is not in $R_2$, the relation $R_2$ is not symmetric. (No need to check other pairs).
- (iii) $R_3 = \{(1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3, 2)\}$
Check pairs where $a \neq b$:
- $(1, 2) \in R_3$. Is $(2, 1) \in R_3$? Yes.
- $(2, 1) \in R_3$. Is $(1, 2) \in R_3$? Yes.
- $(1, 3) \in R_3$. Is $(3, 1) \in R_3$? Yes.
- $(3, 1) \in R_3$. Is $(1, 3) \in R_3$? Yes.
- $(2, 3) \in R_3$. Is $(3, 2) \in R_3$? Yes.
- $(3, 2) \in R_3$. Is $(2, 3) \in R_3$? Yes.
All pairs have their reverses present in $R_3$.
The relation $R_3$ is symmetric.
- (iv) $R_4 = \{(a, b) \in A \times A \mid a + b = 4\}$
We need to check: If $(a, b) \in R_4$, does $(b, a)$ also satisfy the condition $b + a = 4$?
Assume $(a, b) \in R_4$. This means $a, b \in A$ and $a + b = 4$.
Consider the reverse pair $(b, a)$. The sum of its components is $b + a$. Since addition is commutative ($a + b = b + a$), if $a + b = 4$, then $b + a = 4$.
So, if $(a, b) \in R_4$, then $(b, a)$ must also be in $R_4$.
The relation $R_4$ is symmetric.
(Let's find $R_4$ in roster form to verify: $A=\{1, 2, 3\}$. Pairs $(a, b)$ with $a+b=4$: $(1, 3), (3, 1), (2, 2)$. $R_4 = \{(1, 3), (3, 1), (2, 2)\}$. Checking pairs: $(1, 3)$ reverse is $(3, 1)$, which is in $R_4$. $(3, 1)$ reverse is $(1, 3)$, which is in $R_4$. $(2, 2)$ is a diagonal pair. So $R_4$ is symmetric).
- (v) $R_5 = \{(a, b) \in A \times A \mid a \le b\}$
We need to check: If $(a, b) \in R_5$, does it imply $(b, a) \in R_5$?
Assume $(a, b) \in R_5$. This means $a \le b$.
For $(b, a)$ to be in $R_5$, we must have $b \le a$.
Does $a \le b$ always imply $b \le a$? No. For example, if $a=1$ and $b=2$, then $1 \le 2$ is true, so $(1, 2) \in R_5$. But $2 \le 1$ is false, so $(2, 1) \notin R_5$.
Since $(1, 2) \in R_5$ but $(2, 1) \notin R_5$, the relation $R_5$ is not symmetric.
(In roster form, $R_5 = \{(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)\}$. The pair $(1, 2)$ is present, but $(2, 1)$ is missing. The pair $(1, 3)$ is present, but $(3, 1)$ is missing. The pair $(2, 3)$ is present, but $(3, 2)$ is missing. This confirms it's not symmetric).
Transitive Relation
A relation $R$ on a set $A$ is called transitive if, whenever there is a chain of relations from $a$ to $b$ and from $b$ to $c$, there must also be a direct relation from $a$ to $c$. It captures the idea of a "chain reaction" or implication across elements.
Definition of Transitive Relation
A relation $R$ on a set $A$ is said to be transitive if and only if for all elements $a, b, c$ in set $A$, whenever the ordered pair $(a, b)$ is in $R$ and the ordered pair $(b, c)$ is in $R$, it implies that the ordered pair $(a, c)$ must also be in $R$.
Formal Condition:
A relation $R$ on $A$ is transitive $\iff \forall a, b, c \in A, [(a, b) \in R \land (b, c) \in R] \implies (a, c) \in R$
Here, $a, b, c$ do not have to be distinct elements. The condition must be checked for all possible elements $a, b, c$ from the set $A$.
Important Notes:
- The core of transitivity is checking the "links". If you have a sequence of related pairs where the second element of one pair is the first element of another, like $(a, \underline{b})$ and $(\underline{b}, c)$, you must check if the "shortcut" pair $(a, c)$ exists in the relation.
- If there is no such sequence of pairs (i.e., if for specific $a, b, c$, either $(a, b) \notin R$ or $(b, c) \notin R$), then the premise $[(a, b) \in R \land (b, c) \in R]$ is false, and the implication is vacuously true. In this case, that combination of $a, b, c$ does not violate transitivity.
- The empty relation ($\emptyset$) on any set A is transitive because the premise $(a, b) \in \emptyset \land (b, c) \in \emptyset$ is always false.
- The universal relation ($A \times A$) on any set A is transitive because if $(a, b) \in A \times A$ and $(b, c) \in A \times A$, then $(a, c)$ is also always in $A \times A$.
- The identity relation ($I_A$) on any set A is transitive. If $(a, b) \in I_A$ and $(b, c) \in I_A$, then we must have $a=b$ and $b=c$. This implies $a=c$. So, the implied pair is $(a, a)$, which is always in $I_A$.
How to Check if a Relation is Transitive
To check if a given relation $R$ on a set $A$ is transitive, follow these steps:
- Examine the relation $R$ and look for all pairs of ordered pairs $(a, b)$ and $(b, c)$ where the second component of the first pair is the same as the first component of the second pair. The element $b$ acts as the "link".
- For every such "linked" sequence $(a, b) \in R$ and $(b, c) \in R$, identify the corresponding "shortcut" pair $(a, c)$.
- Check if this shortcut pair $(a, c)$ is present in the relation $R$.
- If for every sequence $(a, b) \in R$ and $(b, c) \in R$, the pair $(a, c)$ is also in $R$, the relation is transitive.
- If you find even one instance where $(a, b) \in R$ and $(b, c) \in R$ but $(a, c) \notin R$, stop. The relation is not transitive.
- If there are no such sequences of linked pairs in $R$, the relation is vacuously transitive.
This check can be systematic. List all pairs in $R$. Then, for each pair $(a, b) \in R$, look for all pairs $(b, c) \in R$. If you find any, check for $(a, c)$.
Example 6. Let $A = \{1, 2, 3, 4\}$. Determine if the following relations on A are transitive:
(i) $R_1 = \{(1, 2), (2, 3), (1, 3), (4, 4)\}$
(ii) $R_2 = \{(1, 2), (2, 1), (1, 1), (2, 2)\}$
(iii) $R_3 = \{(1, 2), (2, 3), (3, 1)\}$
(iv) $R_4 = \{(a, b) \in A \times A \mid a \text{ divides } b\}$ (denoted as $a|b$)
(v) $R_5 = \emptyset$
Answer:
Given: Set $A = \{1, 2, 3, 4\}$.
- (i) $R_1 = \{(1, 2), (2, 3), (1, 3), (4, 4)\}$
Check for linked pairs $(a, b), (b, c)$ in $R_1$:
- $(1, \underline{2}) \in R_1$ and $(\underline{2}, 3) \in R_1$. This is a link with $b=2$. The shortcut pair is $(a, c) = (1, 3)$. Is $(1, 3) \in R_1$? Yes.
- $(4, \underline{4}) \in R_1$ and $(\underline{4}, 4) \in R_1$. This is a link with $b=4$. The shortcut pair is $(a, c) = (4, 4)$. Is $(4, 4) \in R_1$? Yes.
These are the only sequences of linked pairs in $R_1$. In all cases, the shortcut pair is present.
The relation $R_1$ is transitive.
- (ii) $R_2 = \{(1, 2), (2, 1), (1, 1), (2, 2)\}$
Check for linked pairs $(a, b), (b, c)$ in $R_2$:
- $(1, \underline{2}) \in R_2$ and $(\underline{2}, 1) \in R_2$. Link $b=2$. Shortcut is $(1, 1)$. Is $(1, 1) \in R_2$? Yes.
- $(2, \underline{1}) \in R_2$ and $(\underline{1}, 2) \in R_2$. Link $b=1$. Shortcut is $(2, 2)$. Is $(2, 2) \in R_2$? Yes.
- $(1, \underline{1}) \in R_2$ and $(\underline{1}, 1) \in R_2$. Link $b=1$. Shortcut is $(1, 1)$. Is $(1, 1) \in R_2$? Yes.
- $(1, \underline{1}) \in R_2$ and $(\underline{1}, 2) \in R_2$. Link $b=1$. Shortcut is $(1, 2)$. Is $(1, 2) \in R_2$? Yes.
- $(2, \underline{2}) \in R_2$ and $(\underline{2}, 1) \in R_2$. Link $b=2$. Shortcut is $(2, 1)$. Is $(2, 1) \in R_2$? Yes.
- $(2, \underline{2}) \in R_2$ and $(\underline{2}, 2) \in R_2$. Link $b=2$. Shortcut is $(2, 2)$. Is $(2, 2) \in R_2$? Yes.
All required implications hold.
The relation $R_2$ is transitive.
- (iii) $R_3 = \{(1, 2), (2, 3), (3, 1)\}$
Check for linked pairs $(a, b), (b, c)$ in $R_3$:
- $(1, \underline{2}) \in R_3$ and $(\underline{2}, 3) \in R_3$. Link $b=2$. Shortcut is $(1, 3)$. Is $(1, 3) \in R_3$? No.
Since $(1, 2) \in R_3$ and $(2, 3) \in R_3$ but $(1, 3) \notin R_3$, the relation $R_3$ is not transitive.
(We could also check $(2, \underline{3}) \in R_3$ and $(\underline{3}, 1) \in R_3 \implies (2, 1) \notin R_3$, or $(\underline{3}, 1) \in R_3$ and $(\underline{1}, 2) \in R_3 \implies (3, 2) \notin R_3$).
- (iv) $R_4 = \{(a, b) \in A \times A \mid a \text{ divides } b\}$
We need to check: If $(a, b) \in R_4$ and $(b, c) \in R_4$, does it imply $(a, c) \in R_4$?
$(a, b) \in R_4$ means $a$ divides $b$ (i.e., $b = ka$ for some integer $k$). Since $a,b \in A \subseteq \mathbb{N}$, $k$ must be a natural number.
$(b, c) \in R_4$ means $b$ divides $c$ (i.e., $c = lb$ for some natural number $l$).
Now substitute the first equation into the second: $c = l(ka) = (lk)a$.
Since $k$ and $l$ are natural numbers, their product $lk$ is also a natural number. This equation $c = (lk)a$ means that $a$ divides $c$.
Therefore, if $a$ divides $b$ and $b$ divides $c$, then $a$ divides $c$. This means if $(a, b) \in R_4$ and $(b, c) \in R_4$, then $(a, c) \in R_4$.
The relation $R_4$ (divisibility relation) on $A$ is transitive.
- (v) $R_5 = \emptyset$
The empty relation has no ordered pairs. Thus, there are no pairs $(a, b)$ and $(b, c)$ in $R_5$ for any $a, b, c \in A$.
The premise $[(a, b) \in R_5 \land (b, c) \in R_5]$ is always false.
Therefore, the implication is vacuously true for all $a, b, c \in A$.
The empty relation $R_5$ is transitive.
Summary for Competitive Exams
Symmetric Relation: $R$ on $A$ is symmetric $\iff \forall a, b \in A, (a, b) \in R \implies (b, a) \in R$.
- If $(a, b) \in R$ where $a \neq b$, $(b, a)$ must also be in $R$.
- Pairs $(a, a)$ do not affect symmetry.
Transitive Relation: $R$ on $A$ is transitive $\iff \forall a, b, c \in A, [(a, b) \in R \land (b, c) \in R] \implies (a, c) \in R$.
- If you have a chain $(a, b)$ and $(b, c)$ in R, the "shortcut" $(a, c)$ must also be in R.
- If no such chain exists, the relation is vacuously transitive.
Identity, Empty, Universal Relations Properties:
- $I_A$: Reflexive, Symmetric, Transitive.
- $\emptyset$ (on non-empty A): NOT Reflexive, Symmetric, Transitive.
- $A \times A$: Reflexive, Symmetric, Transitive.
Equivalence Relation and Equivalence Classes
Equivalence relations are a very important class of relations in mathematics because they capture the concept of "sameness" or "being alike" in a structured way. They allow us to group elements of a set based on a shared property defined by the relation.
Equivalence Relation
A relation $R$ on a set $A$ is defined as an equivalence relation if it simultaneously satisfies all three of the following fundamental properties:
-
Reflexive:
For every element $a$ in set $A$, $a$ is related to itself.$\forall a \in A, (a, a) \in R$
-
Symmetric:
For any two elements $a$ and $b$ in set $A$, if $a$ is related to $b$, then $b$ must also be related to $a$.$\forall a, b \in A, (a, b) \in R \implies (b, a) \in R$
-
Transitive:
For any three elements $a, b$, and $c$ in set $A$, if $a$ is related to $b$, and $b$ is related to $c$, then $a$ must also be related to $c$.$\forall a, b, c \in A, [(a, b) \in R \land (b, c) \in R] \implies (a, c) \in R$
If a relation $R$ on a set $A$ satisfies all three of these properties, it is an equivalence relation. Equivalence relations are crucial in mathematics because they partition the set $A$ into non-overlapping subsets, where all elements within a subset are related to each other, and no element is related to an element outside its subset. These subsets are called equivalence classes.
Example 1. Let $L$ be the set of all lines in a plane. Define a relation $R$ on $L$ by $R = \{(l_1, l_2) \mid l_1 \text{ is parallel to } l_2\}$. Show that R is an equivalence relation.
(Assume that any line is parallel to itself).
Answer:
Given: Set $L$ of all lines in a plane, Relation $R = \{(l_1, l_2) \mid l_1, l_2 \in L, l_1 \parallel l_2\}$.
To Show: R is an equivalence relation.
We need to check if R satisfies reflexivity, symmetry, and transitivity.
1. Reflexivity:
For any line $l \in L$, is $(l, l) \in R$? This means, is $l$ parallel to itself ($l \parallel l$)?
By the assumption given (which is standard in geometry), any line is parallel to itself.
Thus, $(l, l) \in R$ for all $l \in L$.
Therefore, R is reflexive.
(If the assumption "any line is parallel to itself" was not given, the relation might not be reflexive, e.g., some definitions of parallel lines require them to be distinct and non-intersecting).
2. Symmetry:
For any lines $l_1, l_2 \in L$, if $(l_1, l_2) \in R$, does it imply $(l_2, l_1) \in R$?
Assume $(l_1, l_2) \in R$. This means line $l_1$ is parallel to line $l_2$ ($l_1 \parallel l_2$).
If $l_1$ is parallel to $l_2$, it is a geometric property that $l_2$ is also parallel to $l_1$ ($l_2 \parallel l_1$).
So, $(l_2, l_1) \in R$.
Therefore, R is symmetric.
3. Transitivity:
For any lines $l_1, l_2, l_3 \in L$, if $(l_1, l_2) \in R$ and $(l_2, l_3) \in R$, does it imply $(l_1, l_3) \in R$?
Assume $(l_1, l_2) \in R$ and $(l_2, l_3) \in R$.
This means $l_1 \parallel l_2$ and $l_2 \parallel l_3$.
It is a well-known property from Euclidean geometry that if a line is parallel to a second line, and the second line is parallel to a third line, then the first line is parallel to the third line (provided all lines are in the same plane). That is, if $l_1 \parallel l_2$ and $l_2 \parallel l_3$, then $l_1 \parallel l_3$.
So, $(l_1, l_3) \in R$.
Therefore, R is transitive.
Since the relation R is reflexive, symmetric, and transitive, it is an equivalence relation on the set of lines L.
Equivalence Classes
If $R$ is an equivalence relation on a set $A$, it partitions the set $A$ into subsets called equivalence classes. Each equivalence class consists of elements that are all related to each other under the relation $R$.
Definition of Equivalence Class:
For any element $a \in A$, the equivalence class of $a$, denoted by $[a]$ (read as "the equivalence class of a") or sometimes $\bar{a}$, is the set of all elements in $A$ that are related to $a$ by the relation $R$.
$[a] = \{ x \in A \mid (x, a) \in R \}$
Because an equivalence relation is symmetric, the condition $(x, a) \in R$ is equivalent to $(a, x) \in R$. So, the definition can also be written as:
$[a] = \{ x \in A \mid (a, x) \in R \}$
Properties of Equivalence Classes
Let $R$ be an equivalence relation on a set $A$. The collection of all distinct equivalence classes of $A$ forms a partition of the set $A$. This means the following properties hold:
-
Classes are non-empty:
For any $a \in A$, the element $a$ itself belongs to its equivalence class $[a]$ because $R$ is reflexive (so $(a, a) \in R$). Thus, $[a] \neq \emptyset$. -
Any two equivalence classes are either identical or disjoint:
For any two elements $a, b \in A$, their equivalence classes $[a]$ and $[b]$ are either exactly the same set ($[a] = [b]$) or they have no elements in common ($[a] \cap [b] = \emptyset$). This means distinct equivalence classes do not overlap.
Specifically:- If $(a, b) \in R$ (i.e., $a$ and $b$ are related), then their equivalence classes are the same: $[a] = [b]$.
- If $(a, b) \notin R$ (i.e., $a$ and $b$ are not related), then their equivalence classes are disjoint: $[a] \cap [b] = \emptyset$.
-
The union of all distinct equivalence classes is the entire set:
Every element of $A$ belongs to one and only one equivalence class. The union of all the distinct equivalence classes is equal to the original set $A$.$\bigcup_{a \in A} [a] = A$
These properties show that an equivalence relation divides a set into mutually exclusive categories (the equivalence classes).
Example 2. Let $A = \{1, 2, 3, 4, 5, 6\}$. Let $R$ be the relation on $A$ defined by $R = \{(a, b) \mid a, b \in A \text{ and } a - b \text{ is divisible by 2}\}$. Show R is an equivalence relation and find the equivalence classes.
Answer:
Given: Set $A = \{1, 2, 3, 4, 5, 6\}$. Relation $R = \{(a, b) \mid a, b \in A, 2 \mid (a - b)\}$.
To Show: R is an equivalence relation and find the equivalence classes.
We check the three properties:
1. Reflexivity:
For any $a \in A$, is $(a, a) \in R$? This means, is $a - a$ divisible by 2?
$a - a = 0$. $0$ is divisible by 2 (since $0 = 2 \times 0$).
So, $(a, a) \in R$ for all $a \in A$. R is reflexive.
2. Symmetry:
For any $a, b \in A$, if $(a, b) \in R$, does it imply $(b, a) \in R$?
Assume $(a, b) \in R$. This means $a - b$ is divisible by 2. So, $a - b = 2k$ for some integer $k$.
Consider $b - a$. $b - a = -(a - b) = -(2k) = 2(-k)$. Since $k$ is an integer, $-k$ is also an integer.
So, $b - a$ is divisible by 2. This means $(b, a) \in R$.
Therefore, R is symmetric.
3. Transitivity:
For any $a, b, c \in A$, if $(a, b) \in R$ and $(b, c) \in R$, does it imply $(a, c) \in R$?
Assume $(a, b) \in R$ and $(b, c) \in R$.
$(a, b) \in R \implies a - b$ is divisible by 2, so $a - b = 2k$ for some integer $k$.
$(b, c) \in R \implies b - c$ is divisible by 2, so $b - c = 2l$ for some integer $l$.
We want to check if $a - c$ is divisible by 2. Consider $a - c = (a - b) + (b - c)$.
$a - c = 2k + 2l = 2(k + l)$. Since $k$ and $l$ are integers, $k + l$ is an integer.
So, $a - c$ is divisible by 2. This means $(a, c) \in R$.
Therefore, R is transitive.
Since R is reflexive, symmetric, and transitive, it is an equivalence relation on the set A.
Equivalence Classes:
The relation $a - b$ is divisible by 2 is equivalent to saying that $a$ and $b$ have the same parity (both even or both odd).
Let's find the equivalence class for each element in A:
- $[1] = \{x \in A \mid (x, 1) \in R\}$. This means $x \in A$ and $x - 1$ is divisible by 2, i.e., $x$ and 1 have the same parity. Since 1 is odd, we need the odd numbers in A.
$[1] = \{1, 3, 5\}$.
- $[2] = \{x \in A \mid (x, 2) \in R\}$. This means $x \in A$ and $x - 2$ is divisible by 2, i.e., $x$ and 2 have the same parity. Since 2 is even, we need the even numbers in A.
$[2] = \{2, 4, 6\}$.
- $[3] = \{x \in A \mid (x, 3) \in R\}$. This means $x \in A$ and $x - 3$ is divisible by 2, i.e., $x$ and 3 have the same parity. Since 3 is odd, we need the odd numbers in A.
$[3] = \{1, 3, 5\}$.
- $[4] = \{x \in A \mid (x, 4) \in R\}$. This means $x \in A$ and $x - 4$ is divisible by 2, i.e., $x$ and 4 have the same parity. Since 4 is even, we need the even numbers in A.
$[4] = \{2, 4, 6\}$.
- $[5] = \{x \in A \mid (x, 5) \in R\}$. This means $x \in A$ and $x - 5$ is divisible by 2, i.e., $x$ and 5 have the same parity. Since 5 is odd, we need the odd numbers in A.
$[5] = \{1, 3, 5\}$.
- $[6] = \{x \in A \mid (x, 6) \in R\}$. This means $x \in A$ and $x - 6$ is divisible by 2, i.e., $x$ and 6 have the same parity. Since 6 is even, we need the even numbers in A.
$[6] = \{2, 4, 6\}$.
We observe that there are only two distinct equivalence classes:
- $[1] = [3] = [5] = \{1, 3, 5\}$ (the set of odd numbers in A)
- $[2] = [4] = [6] = \{2, 4, 6\}$ (the set of even numbers in A)
The set of distinct equivalence classes is $\{\{1, 3, 5\}, \{2, 4, 6\}\}$.
Let's check the partition properties:
- Are the classes non-empty? Yes, $\{1, 3, 5\}$ and $\{2, 4, 6\}$ are non-empty.
- Are they mutually disjoint? Yes, $\{1, 3, 5\} \cap \{2, 4, 6\} = \emptyset$.
- Is their union the entire set A? Yes, $\{1, 3, 5\} \cup \{2, 4, 6\} = \{1, 2, 3, 4, 5, 6\} = A$.
This confirms that the distinct equivalence classes form a partition of the set A.
Summary for Competitive Exams
Equivalence Relation: A relation $R$ on a set $A$ that is simultaneously:
- Reflexive: $\forall a \in A, (a, a) \in R$.
- Symmetric: $\forall a, b \in A, (a, b) \in R \implies (b, a) \in R$.
- Transitive: $\forall a, b, c \in A, [(a, b) \in R \land (b, c) \in R] \implies (a, c) \in R$.
Equivalence Class of $a$ ($[a]$): For an equivalence relation $R$ on $A$, the set of all elements in $A$ related to $a$.
$[a] = \{x \in A \mid (x, a) \in R\}$
Properties of Equivalence Classes:
- They are non-empty ($a \in [a]$).
- Any two classes are either identical ($[a]=[b]$ if $(a, b) \in R$) or disjoint ($[a] \cap [b] = \emptyset$ if $(a, b) \notin R$).
- They form a partition of the set A (union is A, distinct classes are disjoint).
Equivalence relations classify elements into groups of mutually related elements.